package find;

//字符串中的查找
public class KMP {

	public static void main(String[] args) {
//		String pattern = "abbabbbabaa";
		String pattern = "aba";
		int[] next = new int[pattern.length()];
		System.out.println("-----");
//		kmp("ababaabbbb ababbaabaa abaabbaaaa bbabaabbbb bbabbaabba bbbabbbbba" +
//				"aabaababbb aabbbabbba abbbbaaabb ababbabbba baaabbaabb" +
//				"abababbbaa aaaaababba baababaabb bbaaabbbab b", pattern, next);
//		kmp("ababaabbbbababbaabaaabaabbaaaabbabaabbbbbbabbaabbabbbabbbbba" +
//				"aabaababbbaabbbabbbaabbbbaaabbababbabbbabaaabbaabb" +
//				"abababbbaaaaaaababbabaababaabbbbaaabbbabb", pattern, next);
		kmp("abababa", pattern, next);
		for (int i = 0; i < next.length; i++) {
			System.out.print(" " + next[i]);
		}
		System.out.println("-----");
//		find("cccdecccdeccddcd", "ccde");
	}
	
	public static void find(String s, String target){
		char[] chars = s.toCharArray();
		char[] targets = target.toCharArray();
		int k = 0;
		int count = 0;
		for(int j = 0 ; j < chars.length ; ){
            if(chars[j] == targets[k]){
                j++;
                k++;
                if(k >= targets.length){
//                    map.put(A[i], count++);
                	System.out.println("j " + j + "found time : " + count++);
                    k = 0;
                }
            }else{
                //特别注意遍历的顺序，特别是j的顺序，在k>0的时候，说明已经匹配了若干字符但没有匹配满
                //虽然此时的j不能和之前匹配的匹配，但不能算作一开始就不匹配，因此不能++，只能将k置零
                //后返回到原来的j进行匹配判断，这点很容易出错。
                if(k > 0)
                    k = 0;
                else
                    j++;
            }
        }
	}

	public static int kmp(String s, String target, int next[]) {
		int i, q;  //i用于指示chars中的，q用来指示target中的
		char[] chars = s.toCharArray();
		char[] targets = target.toCharArray();
		getNextArray(targets, next);  //生成next数组
		int count = 0;
//		int count1 = 0;  //这个用来看循环执行了几次，仅用于测试
		for (i = 0, q = 0; i < chars.length; ++i) {
			while (q > 0 && targets[q] != chars[i]){
				//System.out.println("countpattern :" + count1 + " i "  + i + " q: " + q);
				//要移动     =  已经匹配的长度(也就是  q)  - next[q - 1]
				//所以最后剩下的匹配长度   =  q - 移动的数目
				//等于next[q - 1]
				q = next[q - 1];
				//count1++;
			}
			//count1 = 0;
			if (targets[q] == chars[i]) {
				q++;
			}
			// 找到匹配的
			if (q == targets.length) {
				System.out.printf("Pattern occurs with shift:%d\n", (i - targets.length + 1));
				count++;
				q = 0;
			}
		}
		return count;
	}
	
	//注意，next数组只与target有关
	// "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
	//next中存储的就是前缀和后缀最长公有元素的长度
	//参考文章：http://www.cnblogs.com/c-cloud/p/3224788.html
	public static void getNextArray(char[] target, int[] next){
		 int q, k = 0;//q:模版字符串target下标；k:最大前后缀长度
		 int length = target.length;
		 next[0] = 0;//模版字符串的第一个字符的最大前后缀长度为0
		 for(q = 1; q < length; q++){
//			 if(target[q] == target[next[q - 1]]){
//		            next[q] = next[q - 1] + 1;
//		     }
			 //退出的条件要么是k等于0，此时后面的if判断中如果相等，那么最大公共长度就是1 
			 //要么就是找到了与target[q]相等的
			 //int count = 0;
			 
			 
			 //既然是移动，那么就不必在里面写while了，原文用的是while，只需写if即可
			 //我错了，还是要使用while，在测试用例中是可以找到的，但是如果不使用while，用if那么就会出现问题
			 //之所以这样是因为kmp的移动并不是一次到位的
			 //abbababb....    查找abbabb时，会出现第6个不匹配，此时kmp算法只移动了3 （5 - 2），所以需要while
			 while(k > 0 && target[q] != target[k]){
				 //这个while循环是整个next函数的关键
				 //如果不相等，就说明P[0]···P[k-1] 与 p[q - 1] ...p[q - k]是匹配成功的，看到这里有没有很熟悉
				 //对的，又是重复利用了Kmp的思想，如果模式串中的不匹配，那么只移动模式串中的值！！！
				 //要移动     =  已经匹配的长度(也就是  k)  - next[k - 1]
				 //所以最后剩下的匹配长度   =  k - 移动的数目
				 //System.out.println("count " + count);
				 k = next[k - 1]; 
			 }
			 //count = 0;
			 //如果相等，那么最大相同前后缀长度加1
			 if(target[q] == target[k]){ 
//				 System.out.println(" kk"+ q + " " + k);
				 k++;
			 }
			 next[q] = k;
//			 System.out.println("nxt " + q +"  "+ next[q]);
		 }
//		 System.out.println(" kk" + k);
//		 for (int i : next) {
//			System.out.print(" " + i);
//		 }
//		 System.out.println("------");
	}
}
